public class Leetcode1220 {

    public static void main(String[] args) {
        System.out.println(countVowelPermutation(144));
        System.out.println(countVowelPermutation(1));
    }

    private static final int MOD = 1000000007;

    public static int countVowelPermutation(int n) {
        long a = 1, e = 1, i = 1, o = 1, u = 1;

        for (int nIndex = 1; nIndex < n; nIndex++) {
            long nextA = (e + u + i) % MOD;
            long nextE = (a + i);
            long nextI = (e + o) % MOD;
            long nextO = i % MOD;
            long nextU = (o + i) % MOD;

            a = nextA;
            e = nextE;
            i = nextI;
            o = nextO;
            u = nextU;
        }

        return (int) ((a + e + i + o + u ) % MOD);
    }
}
